{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Route Between Nodes LCCI "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #图"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findWhetherExistsPath"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #节点间通路"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>节点间通路。给定有向图，设计一个算法，找出两个节点之间是否存在一条路径。</p>\n",
    "\n",
    "<p><strong>示例1:</strong></p>\n",
    "\n",
    "<pre><strong> 输入</strong>：n = 3, graph = [[0, 1], [0, 2], [1, 2], [1, 2]], start = 0, target = 2\n",
    "<strong> 输出</strong>：true\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例2:</strong></p>\n",
    "\n",
    "<pre><strong> 输入</strong>：n = 5, graph = [[0, 1], [0, 2], [0, 4], [0, 4], [0, 1], [1, 3], [1, 4], [1, 3], [2, 3], [3, 4]], start = 0, target = 4\n",
    "<strong> 输出</strong> true\n",
    "</pre>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ol>\n",
    "\t<li>节点数量n在[0, 1e5]范围内。</li>\n",
    "\t<li>节点编号大于等于 0 小于 n。</li>\n",
    "\t<li>图中可能存在自环和平行边。</li>\n",
    "</ol>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [route-between-nodes-lcci](https://leetcode.cn/problems/route-between-nodes-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [route-between-nodes-lcci](https://leetcode.cn/problems/route-between-nodes-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        if start==target:\n",
    "            return True\n",
    "        arr=[[] for _ in range(n)]\n",
    "        for x,y in graph:\n",
    "            arr[x].append(y)\n",
    "        visited=[False]*n\n",
    "        q=[start]\n",
    "        while q:\n",
    "            node=q.pop(0)\n",
    "            if len(arr[node])>0:\n",
    "                if target in arr[node]:\n",
    "                    return True\n",
    "                for x in arr[node]:\n",
    "                    if not visited[x]:\n",
    "                        q.append(x)\n",
    "            visited[node]=True\n",
    "        return False\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        LinkTable = [[] for _ in range(n)]\n",
    "        for u, v in graph:\n",
    "            LinkTable[u].append(v)\n",
    "        vis = deque()\n",
    "        vis.append(start)\n",
    "        visited = set()\n",
    "        while vis:\n",
    "            node = vis.popleft()\n",
    "            visited.add(node)\n",
    "            for edge in LinkTable[node]:\n",
    "                if edge == target:\n",
    "                    return True\n",
    "                elif edge in visited:\n",
    "                    continue\n",
    "                else:\n",
    "                    vis.append(edge) \n",
    "                    \n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        visited = [False] * n\n",
    "        visited[start] = True\n",
    "        first = {start: True}\n",
    "        second = {}\n",
    "\n",
    "        while len(first) > 0:\n",
    "            for g in graph:\n",
    "                if first.get(g[0]):\n",
    "                    if g[1] == target:\n",
    "                        return True\n",
    "\n",
    "                    if not visited[g[1]]:\n",
    "                        visited[g[1]] = True\n",
    "                        second[g[1]] = True\n",
    "\n",
    "            first = {}\n",
    "            for k, v in second.items():\n",
    "                first[k] = v\n",
    "            second = {}\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        dic = collections.defaultdict(list)\n",
    "\n",
    "        for u, v in graph:\n",
    "            dic[u].append(v)\n",
    "\n",
    "        vis = [False] * n\n",
    "        vis[start] = True\n",
    "        q = list()\n",
    "        q.append(start)\n",
    "\n",
    "        while q:\n",
    "            pos = q.pop(0)\n",
    "            if pos == target:\n",
    "                return True\n",
    "            for nxt in dic[pos]:\n",
    "                if not vis[nxt]:\n",
    "                    vis[nxt] = True\n",
    "                    q.append(nxt)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        graph.sort()\n",
    "        hashmap = defaultdict(bool)\n",
    "        hashmap[start] = True\n",
    "        for edge in graph:\n",
    "            if hashmap[edge[0]]:\n",
    "                hashmap[edge[1]] = True\n",
    "        return hashmap[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        visited = [False] * n\n",
    "        visited[start] = True\n",
    "\n",
    "        flag = True\n",
    "\n",
    "        while flag:\n",
    "            flag = False\n",
    "\n",
    "            for g in graph:\n",
    "                if visited[g[0]] and not visited[g[1]]:\n",
    "                    visited[g[1]] = True\n",
    "                    flag = True\n",
    "        return visited[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        dic = collections.defaultdict(list)\n",
    "        #   建立图\n",
    "        for u, v in graph:\n",
    "            dic[u].append(v)\n",
    "        #   记录访问过的节点\n",
    "        vis = set()\n",
    "        q = deque()\n",
    "        q.append(start)\n",
    "        #   BFS\n",
    "        while q:\n",
    "            pos = q.popleft()\n",
    "            if pos == target:\n",
    "                return True\n",
    "            for nxt in dic[pos]:\n",
    "                if nxt not in vis:\n",
    "                    vis.add(nxt)\n",
    "                    q.append(nxt)\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        dict_n = collections.defaultdict(list)\n",
    "        for i in graph:\n",
    "            dict_n[i[0]].append(i[1])\n",
    "\n",
    "        v = set()\n",
    "\n",
    "        q = deque()\n",
    "\n",
    "        q.append(start)\n",
    "\n",
    "        while q:\n",
    "            pos = q.popleft()\n",
    "            if pos == target:\n",
    "                return True\n",
    "            for i in dict_n[pos]:\n",
    "                if i not in v:\n",
    "                    q.append(i)\n",
    "                    v.add(i)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# use a dictionary as a graph\n",
    "# 1. BFS, do a BFS from node a, if we can got node b, there is a path\n",
    "# 2. DFS, do a DFS\n",
    "\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        graph_dic = {i:[] for i in range(n)}\n",
    "        for u, v in graph:\n",
    "            graph_dic[u].append(v)\n",
    "        visited = [False for i in range(n)]\n",
    "        return helper(graph_dic, start, target, visited)\n",
    "\n",
    "def helper(graph, u, target, visited):\n",
    "    if u == target:\n",
    "        return True\n",
    "    visited[u] = True\n",
    "    for v in graph[u]:\n",
    "        if not visited[v]:\n",
    "            if helper(graph, v, target, visited):\n",
    "                return True\n",
    "    return False\n",
    "    \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# use a dictionary as a graph\n",
    "# 1. BFS, do a BFS from node a, if we can got node b, there is a path\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        if start == target:\n",
    "            return True\n",
    "        graph_dic = {i:[] for i in range(n)}\n",
    "        visited = [False for i in range(n)]\n",
    "        for u, v in graph:\n",
    "            if u not in graph_dic:\n",
    "                graph_dic[u] = []\n",
    "            graph_dic[u].append(v)\n",
    "        queue = deque()\n",
    "        queue.append(start)\n",
    "        visited[start] = True\n",
    "        while queue:\n",
    "            u = queue.popleft()\n",
    "            for v in graph_dic[u]:\n",
    "                if v == target:\n",
    "                    return True\n",
    "                if not visited[v]:\n",
    "                    queue.append(v)\n",
    "                    visited[v] = True\n",
    "        return False\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        map = dict()\n",
    "        for i, j in graph:\n",
    "            if map.get(i) != None:\n",
    "                map[i].append(j)\n",
    "            else:\n",
    "                map[i] = [j]\n",
    "        \n",
    "        que = deque()\n",
    "        vst = [0]*n\n",
    "        que.append(start)\n",
    "        vst[start] = 1\n",
    "\n",
    "        while que:\n",
    "            node = que.popleft()\n",
    "            if node == target:\n",
    "                return True\n",
    "            if map.get(node) != None:\n",
    "                for next in map[node]:\n",
    "                    if vst[next] == 0:\n",
    "                        que.append(next)\n",
    "                        vst[next] = 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        if start == target: return True\n",
    "        hashMap = collections.defaultdict(set)\n",
    "        for key, val in graph:\n",
    "            hashMap[key].add(val)\n",
    "        visited = [False] * n\n",
    "        que = []\n",
    "        que.append(start)\n",
    "        while que:\n",
    "            cur = que.pop()\n",
    "            visited[cur] = True\n",
    "            if hashMap[cur]:\n",
    "                if target in hashMap[cur]:\n",
    "                    return True\n",
    "                for node in hashMap[cur]:\n",
    "                    if not visited[node]:\n",
    "                        que.append(node)\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in graph:\n",
    "            g[x].append(y)\n",
    "\n",
    "\n",
    "        seen = set()\n",
    "        def dfs(x):\n",
    "            ret = False\n",
    "            if x == target:\n",
    "                return True\n",
    "            for y in g[x]:\n",
    "                if y not in seen:\n",
    "                    seen.add(y)\n",
    "                    ret |= dfs(y)\n",
    "            return ret\n",
    "        return dfs(start)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        visited = [0] * len(graph)\n",
    "\n",
    "        def find(start, target, path):\n",
    "            for i in range(len(graph)):\n",
    "                if not visited[i]:\n",
    "                    if target == graph[i][1]:\n",
    "                        if start == graph[i][0]:    return True\n",
    "                        visited[i] = 1\n",
    "                        if find(start, graph[i][0], graph[i]):  return True\n",
    "                        visited[i] = 0\n",
    "            return False\n",
    "\n",
    "        return find(start, target, graph[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        visit = set()\n",
    "        s = []\n",
    "        adjs = {}\n",
    "        for g in graph:\n",
    "            if g[0] not in adjs:\n",
    "                adjs[g[0]] = set()\n",
    "            adjs[g[0]].add(g[1])\n",
    "        print(adjs)\n",
    "        s.append(start)\n",
    "        while s!=[]:\n",
    "            lens = len(s)\n",
    "            for i in range(lens):\n",
    "                p = s[i]\n",
    "                if p in visit:\n",
    "                    continue\n",
    "                visit.add(p)\n",
    "                if p not in adjs:\n",
    "                    continue\n",
    "                for b in adjs[p]:\n",
    "                    if target == b:\n",
    "                        return True\n",
    "                    s.append(b)\n",
    "            s = s[lens:]\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        graph_dict = defaultdict(list)\n",
    "        node_set = set()\n",
    "        for head, tail in graph:\n",
    "            graph_dict[head].append(tail)\n",
    "            node_set.add(head)\n",
    "            node_set.add(tail)\n",
    "        def bfs(gd, target):\n",
    "            bfs_queue = [start]\n",
    "            visited_node = set()\n",
    "            while len(visited_node)<len(node_set) and len(bfs_queue)!=0:\n",
    "                pre_len = len(bfs_queue)\n",
    "                for i in bfs_queue:\n",
    "                    if i==target:\n",
    "                        return True\n",
    "                    visited_node.add(i)\n",
    "                    bfs_queue += [j for j in graph_dict[i] if j not in visited_node]\n",
    "                bfs_queue = bfs_queue[pre_len:]\n",
    "            return False\n",
    "        return bfs(graph_dict, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        adj = [[] for _ in range(n)]\n",
    "        for edge in graph:\n",
    "            adj[edge[0]].append(edge[1])\n",
    "\n",
    "        visited = set()\n",
    "        def dfs(vertex):\n",
    "            if vertex == target:\n",
    "                return True\n",
    "            if vertex in visited:\n",
    "                return False\n",
    "            visited.add(vertex)\n",
    "            for v in adj[vertex]:\n",
    "                if dfs(v):\n",
    "                    return True\n",
    "\n",
    "            return False\n",
    "\n",
    "        return dfs(start)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        grap=[[]for i in range(n)]\n",
    "        for x,y in graph:\n",
    "            grap[x].append(y)\n",
    "        def f(x):\n",
    "            if x==target:\n",
    "                return True\n",
    "            nex=grap[x]\n",
    "            for p in nex:\n",
    "                if p not in visited:\n",
    "                    visited.add(p)\n",
    "                    if f(p):\n",
    "                        return True\n",
    "            return False\n",
    "        visited=set()\n",
    "        visited.add(start)\n",
    "        return  f(start)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        hashMap = defaultdict(set)\n",
    "        for key, value in graph:\n",
    "            hashMap[key].add(value)\n",
    "\n",
    "        def dfs(start, target, visited):\n",
    "            if start == target:\n",
    "                return True\n",
    "            if visited[start]:\n",
    "                return False\n",
    "            visited[start] = True\n",
    "            flag = False\n",
    "            if start in hashMap.keys():\n",
    "                for cur in hashMap[start]:\n",
    "                    flag = flag or dfs(cur, target, visited)\n",
    "            return flag\n",
    "\n",
    "        visited = [False] * n\n",
    "        return dfs(start, target, visited)\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        g = defaultdict(list)\n",
    "        for a, b in graph:\n",
    "            g[a].append(b)\n",
    "\n",
    "        vis = {start, }\n",
    "        @cache\n",
    "        def dfs(cur, target) -> bool:\n",
    "            if cur == target:\n",
    "                return True\n",
    "            for nxt in g[cur]:\n",
    "                if nxt not in vis:\n",
    "                    vis.add(nxt)\n",
    "                    if dfs(nxt, target):\n",
    "                        return True\n",
    "            return False\n",
    "\n",
    "        return dfs(start, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "       \n",
    "        visit = [0] * (n+1)\n",
    "        graph_path = [[] for _ in range(n+1)]\n",
    "        for pair in graph:\n",
    "            graph_path[pair[0]].append(pair[1])\n",
    "\n",
    "        # # bfs\n",
    "        # node_que = []\n",
    "        # node_que.append(start)\n",
    "        # visit[start] = 1\n",
    "        # while len(node_que) != 0:\n",
    "        #     now = node_que.pop(0)\n",
    "        #     for next_node in graph_path[now]:\n",
    "        #         if next_node == target:\n",
    "        #             return True\n",
    "        #         if visit[next_node] == 0:\n",
    "        #             node_que.append(next_node)\n",
    "        #             visit[next_node] = 1\n",
    "        # return False\n",
    "\n",
    "        # dfs\n",
    "        def dfs(now):\n",
    "            if now  == target:\n",
    "                return True\n",
    "            for next_node in graph_path[now]:\n",
    "                if visit[next_node] == 0:\n",
    "                    visit[next_node] = 1\n",
    "                    if dfs(next_node):\n",
    "                        return True\n",
    "                    # visit[next_node] = 0\n",
    "            return False\n",
    "        \n",
    "        return dfs(start)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        # 自环和平行边\n",
    "        \n",
    "        g = [[]*n for _ in range(n)]\n",
    "        for x,y in graph:\n",
    "            g[x].append(y)\n",
    "\n",
    "        visited = [0]*n \n",
    "\n",
    "        def dfs(x):\n",
    "            if x == target:\n",
    "                return True\n",
    "            for y in g[x]:\n",
    "                if not visited[y]:\n",
    "                    visited[y] = 1\n",
    "                    if dfs(y):\n",
    "                        return True\n",
    "                    visited[y] = 0\n",
    "            return False\n",
    "        visited[start] = 1\n",
    "        return dfs(start)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        vis = [0] * (pow(10, 5) + 1)\n",
    "        obj = {}\n",
    "        for f, t in graph:\n",
    "            if not f in obj:\n",
    "                obj[f] = set()\n",
    "            obj[f].add(t)\n",
    "        \n",
    "        def dfs(i):\n",
    "            if i == target: return True\n",
    "            vis[i] = 1\n",
    "            if not i in obj: return False\n",
    "            for x in obj[i]:\n",
    "                if vis[x] == 0:\n",
    "                    if (dfs(x)): return True\n",
    "            return False\n",
    "\n",
    "        return dfs(start)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        edges =  collections.defaultdict(set)\n",
    "        for i in graph :\n",
    "            edges[i[0]].add(tuple(i))\n",
    "        print(edges)\n",
    "        visited = set()\n",
    "        def dfs(start) :\n",
    "            for i in edges[start]  :\n",
    "                if i[1] == target :\n",
    "                    return True\n",
    "                elif i not in visited :\n",
    "                    if dfs(i[1]) :\n",
    "                        return True \n",
    "            return False \n",
    "        return dfs(start)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "\n",
    "        dic = collections.defaultdict(list)\n",
    "\n",
    "        for u, v in graph:\n",
    "            dic[u].append(v)\n",
    "\n",
    "        vis = [False] * n\n",
    "        def dfs(index):\n",
    "            if index == target:\n",
    "                return True\n",
    "            \n",
    "            if vis[index]:\n",
    "                return False\n",
    "\n",
    "            vis[index] = True\n",
    "            for u in dic[index]:\n",
    "                if dfs(u):\n",
    "                    return True\n",
    "            return False\n",
    "        return dfs(start)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        from collections import defaultdict\n",
    "        g = defaultdict(set)\n",
    "        for u, v in graph:\n",
    "            g[u].add(v)\n",
    "\n",
    "        vis = [False] * n\n",
    "        def dfs(u):\n",
    "            if u == target:\n",
    "                return True\n",
    "            vis[u] = True\n",
    "            for v in g[u]:\n",
    "                if not vis[v] and dfs(v):\n",
    "                    return True\n",
    "            return False\n",
    "        return dfs(start)\n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        dic = {}\n",
    "        for edge in graph:\n",
    "            if edge[0] not in dic:\n",
    "                dic[edge[0]] = [edge[1]]\n",
    "            else:\n",
    "                dic[edge[0]].append(edge[1])\n",
    "        judge = [False] * n\n",
    "        judge[start] = True\n",
    "        def dfs(cur, target) -> bool:\n",
    "            if cur == target:\n",
    "                return True   \n",
    "            if cur not in dic:\n",
    "                return False\n",
    "            for i in dic[cur]:\n",
    "                if not judge[i]:\n",
    "                    judge[i] = True\n",
    "                    if dfs(i, target):\n",
    "                        return True\n",
    "                    judge[i] = False\n",
    "            return False   \n",
    "        return dfs(start, target)  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        dic = defaultdict(set)\n",
    "        for u,v in graph:\n",
    "            dic[u].add(v)\n",
    "        visited = [False]*n\n",
    "\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(start,targrt):\n",
    "            if start == target:\n",
    "                return True\n",
    "            if visited[start]:\n",
    "                return False\n",
    "            visited[start] = True\n",
    "            res = False\n",
    "            for nxt in dic[start]:\n",
    "                res = res or dfs(nxt,target)\n",
    "            return res\n",
    "        res = dfs(start,target)\n",
    "        return res \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        dic = {}   # 找到各节点的邻节点\n",
    "        visited = {}   # 记录节点是否被访问\n",
    "        for i in range(n):\n",
    "            dic[i] = []\n",
    "            visited[i] = False  # 初始化\n",
    "        for node in graph:\n",
    "            dic.get(node[0]).append(node[1])\n",
    "        visited[start] = True\n",
    "        path = []\n",
    "        path.append(start)\n",
    "        while path:\n",
    "            cur = path[-1]\n",
    "            if cur == target:\n",
    "                return True\n",
    "            for node in dic[cur]:\n",
    "                if visited[node]:\n",
    "                    continue\n",
    "                path.append(node)\n",
    "                visited[node] = True\n",
    "                break\n",
    "            else:\n",
    "                path.pop()\n",
    "        return False\n",
    "\n",
    "\n",
    "        # while path:\n",
    "        #     li = graph.copy()\n",
    "        #     cur = path.popleft()\n",
    "        #     passed.append(cur)\n",
    "        #     if target == cur:\n",
    "        #         return True\n",
    "        #     for node in li:\n",
    "        #         if node[0] == cur and node[1] not in passed:\n",
    "        #             path.append(node[1])\n",
    "        #             graph.remove(node)\n",
    "        # li.clear()\n",
    "        # return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        nodemap = {i:[i] for i in range(n)}\n",
    "        for item in graph:\n",
    "            if item[0] in nodemap:\n",
    "                nodemap[item[0]].append(item[1])\n",
    "            else:\n",
    "                nodemap[item[0]] = [item[1]]\n",
    "        queen = [start]\n",
    "        visit = set()\n",
    "        visit.add(start)\n",
    "        while queen:\n",
    "            n = len(queen)\n",
    "            for _ in range(n):\n",
    "                anode = queen.pop(0)\n",
    "                midmap = nodemap[anode] if nodemap[anode] else []\n",
    "                if target in nodemap[anode]:\n",
    "                    return True\n",
    "                for item in midmap:\n",
    "                    if item not in visit:\n",
    "                        queen.append(item)\n",
    "                        visit.add(item)\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        # neighbor table\n",
    "        nt = [set() for _ in range(n)]\n",
    "        for e in graph:\n",
    "            nt[e[0]].add(e[1])\n",
    "        # print(nt)\n",
    "        # traversed?\n",
    "        \n",
    "        stack = [start]\n",
    "        dic = {}\n",
    "        while stack:\n",
    "            x = stack.pop()\n",
    "            if not dic.get(x, None):\n",
    "                print(nt[x])\n",
    "                for y in nt[x]:\n",
    "                    if target == y:\n",
    "                        return True\n",
    "                    else:\n",
    "                        stack.append(y)\n",
    "            \n",
    "                dic[x] = True\n",
    "        \n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        # neighbor table\n",
    "        nt = [set() for _ in range(n)]\n",
    "        for e in graph:\n",
    "            nt[e[0]].add(e[1])\n",
    "        # print(nt)\n",
    "        # traversed?\n",
    "        \n",
    "        stack = [start]\n",
    "        dic = {}\n",
    "        while stack:\n",
    "            x = stack.pop()\n",
    "            if not dic.get(x, None):\n",
    "                print(nt[x])\n",
    "                for y in nt[x]:\n",
    "                    if target == y:\n",
    "                        return True\n",
    "                    else:\n",
    "                        stack.append(y)\n",
    "            \n",
    "                dic[x] = True\n",
    "        \n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        if [start, target] in graph:\n",
    "            return True\n",
    "        dic = collections.defaultdict(set)\n",
    "        for k, v in graph:\n",
    "            dic[k].add(v)\n",
    "        stack = [start]\n",
    "        while stack:\n",
    "            t = stack.pop()\n",
    "            if t == target:\n",
    "                return True\n",
    "            for j in dic[t]:\n",
    "                stack.append(j)\n",
    "        return False\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        queue = collections.deque()\n",
    "        adjacent_dict = {idx: [] for idx in range(n)}\n",
    "        visited = {idx: False for idx in range(n)}\n",
    "        for edge in graph:\n",
    "            if edge[0] != edge[1]:\n",
    "                adjacent_dict[edge[0]].append(edge[1])\n",
    "        queue.appendleft(start)\n",
    "        visited[start] = True\n",
    "        while queue and not visited[target]:\n",
    "            cur = queue.pop()\n",
    "            for node in adjacent_dict[cur]:\n",
    "                visited[node] = True\n",
    "                queue.appendleft(node)\n",
    "        return visited[target]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        # dfs 或 bfs\n",
    "        # 用visited记录已经走过的点\n",
    "        seen=set()\n",
    "        g=[list() for _ in range(n)]\n",
    "        tmpset=set()\n",
    "        for s,e in graph:\n",
    "            if s==e or (s,e) in tmpset:continue\n",
    "            tmpset.add((s,e))\n",
    "            g[s].append(e)\n",
    "        # print(g)\n",
    "        def dfs(cur,target):\n",
    "            # print(cur)\n",
    "            if cur==target:return True\n",
    "            seen.add(cur)\n",
    "            for child in g[cur]:\n",
    "                if child not in seen:\n",
    "                    if dfs(child,target):return True\n",
    "            seen.remove(cur)\n",
    "            return False\n",
    "        return dfs(start,target)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        if start < 0 or target < 0 or start > n or target > n or not graph:\n",
    "            return False\n",
    "        directs = {i:[] for i in range(n)}\n",
    "        \n",
    "        for s, e in graph:\n",
    "            directs[s].append(e)\n",
    "        path = {i:False for i in range(n)}\n",
    "        path[start] = True\n",
    "        cur = directs[start]\n",
    "        while cur:\n",
    "            nxt = []\n",
    "            for n in cur:\n",
    "                if n == target:\n",
    "                    return True\n",
    "                if not path[n]:\n",
    "                    nxt.extend(directs[n])\n",
    "                    path[n] = True\n",
    "                else:\n",
    "                    print(n)\n",
    "                    continue\n",
    "            cur = nxt\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque, defaultdict\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        g = defaultdict(set)\n",
    "        for x, y in graph:\n",
    "            g[x].add(y)\n",
    "        roots = deque([start])\n",
    "        visited = [False] * n\n",
    "        while roots:\n",
    "            node = roots.popleft()\n",
    "            visited[node] = True\n",
    "            for x in g[node]:\n",
    "                if x == target:\n",
    "                    return True\n",
    "                if not visited[x]:\n",
    "                    roots.append(x)\n",
    "            # roots = deque(set(roots))\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.visited = {}\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        def dfs(graph: List[List[int]], start: int, target: int):\n",
    "            lens = len(graph)\n",
    "            for i in range(lens):\n",
    "                if i in self.visited and self.visited[i]:\n",
    "                    continue\n",
    "                self.visited[i] = True\n",
    "                if graph[i][0] == start and graph[i][1] == target:\n",
    "                    return True\n",
    "                if graph[i][1] == target and dfs(graph, start, graph[i][0]):\n",
    "                    return True\n",
    "                # 清除标记\n",
    "                self.visited[i] = False\n",
    "            return False\n",
    "        return dfs(graph, start, target)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        visitied = [False]*n\n",
    "        graphdict = collections.defaultdict(set)\n",
    "        for s,t in graph:\n",
    "            graphdict[s].add(t)\n",
    "        def dfs(sta):\n",
    "            if visitied[sta]:\n",
    "                return False\n",
    "            visitied[sta] = True\n",
    "            if target in graphdict[sta]:\n",
    "                return True\n",
    "            for c in graphdict[sta]:\n",
    "                if dfs(c):\n",
    "                    return True\n",
    "            return False\n",
    "        return dfs(start)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        visitied = [False]*n\n",
    "        graphdict = collections.defaultdict(set)\n",
    "        for s,t in graph:\n",
    "            graphdict[s].add(t)\n",
    "        def dfs(sta):\n",
    "            if visitied[sta]:\n",
    "                return False\n",
    "            visitied[sta] = True\n",
    "            if target in graphdict[sta]:\n",
    "                return True\n",
    "            for c in graphdict[sta]:\n",
    "                if dfs(c):\n",
    "                    return True\n",
    "            return False\n",
    "        return dfs(start)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        visitied = [False]*n\n",
    "        graphdict = collections.defaultdict(set)\n",
    "        for s,t in graph:\n",
    "            graphdict[s].add(t)\n",
    "        def dfs(sta):\n",
    "            if visitied[sta]:\n",
    "                return False\n",
    "            visitied[sta] = True\n",
    "            if target in graphdict[sta]:\n",
    "                return True\n",
    "            for c in graphdict[sta]:\n",
    "                if dfs(c):\n",
    "                    return True\n",
    "            return False\n",
    "        return dfs(start)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        b=collections.defaultdict(set)\n",
    "        # print(b.items())\n",
    "        for star,end in graph:\n",
    "            b[star].add(end)\n",
    "        # print(b.items())\n",
    "        # print(b[start])\n",
    "        # lis=[]\n",
    "        def bfs(start,end):\n",
    "            ls=b[start]\n",
    "            if end in ls:\n",
    "                return True\n",
    "            cur=set()\n",
    "            # print(b[start])\n",
    "            # print(ls)\n",
    "            while ls:\n",
    "                c=ls.pop()\n",
    "                # lis.append(c)\n",
    "                cur=cur.union(b[c])\n",
    "                # print(ls)\n",
    "                # print(cur)\n",
    "                if not ls and cur:\n",
    "                    ls=cur\n",
    "                    # print(ls)\n",
    "                    if end in ls:\n",
    "                        return True\n",
    "                    cur=set()\n",
    "            else:\n",
    "                return False\n",
    "        return bfs(start,target)\n",
    "        # return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        parents = [set() for _ in range(n)]\n",
    "        for parent, end in graph:\n",
    "            parents[end].add(parent)\n",
    "\n",
    "        q = [target]\n",
    "        visited = set()\n",
    "        while q:\n",
    "            node = q.pop(0)\n",
    "            if node == start:\n",
    "                return True\n",
    "            visited.add(node)\n",
    "            for parent in parents[node]:\n",
    "                if parent not in visited:\n",
    "                    q.append(parent)\n",
    "            \n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        path_node_set = set()\n",
    "        node_list = [start]\n",
    "        node_path_list = [set() for i in range(n)]\n",
    "        \n",
    "        for item in graph:\n",
    "            node_path_list[item[0]].add(item[1])\n",
    "        #print(node_path_list)\n",
    "        while len(node_list) > 0:\n",
    "            for item in node_path_list[node_list[0]]:\n",
    "                if item == target:\n",
    "                    return True\n",
    "                if item not in path_node_set:\n",
    "                    path_node_set.add(item)\n",
    "                    node_list.append(item)\n",
    "            node_list.pop(0)\n",
    "            #print(node_list)\n",
    " \n",
    "        return False\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        dic = defaultdict(set)# 用字典来构建邻接表\n",
    "        for u,v in graph:\n",
    "            dic[u].add(v)\n",
    "        visited = [False]*n\n",
    "\n",
    "        queue = [start]\n",
    "        while queue:\n",
    "            cur  = queue.pop(0)\n",
    "            visited[cur] = True\n",
    "            if len(dic[start])>0:\n",
    "                if target in dic[cur]:\n",
    "                    return True\n",
    "                for next in dic[cur]:\n",
    "                    if not visited[next]:\n",
    "                        queue.append(next)\n",
    "        return False\n",
    "\n",
    "    \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        if start == target:\n",
    "            return True\n",
    "        \n",
    "        hashMap = defaultdict(set)\n",
    "        for key, value in graph:\n",
    "            hashMap[key].add(value)\n",
    "        visited = [False] * n\n",
    "        queue = []\n",
    "        queue.append(start)\n",
    "        while queue:\n",
    "            cur = queue.pop(0)\n",
    "            visited[cur] = True\n",
    "            if len(hashMap[cur]) > 0:\n",
    "                if target in hashMap[cur]:\n",
    "                    return True\n",
    "                for point in hashMap[cur]:\n",
    "                    if not visited[point]:\n",
    "                        queue.append(point)\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        if start==target:\n",
    "            return True\n",
    "        # 构建邻接表\n",
    "        hashMap = defaultdict(set)\n",
    "        for key, value in graph:  # 用字典来构建邻接表\n",
    "            hashMap[key].add(value)\n",
    "        visited = [False] * n # 记录遍历过的顶点，防止环的情况出现\n",
    "        queue = []\n",
    "        queue.append(start)\n",
    "        while queue:\n",
    "            cur = queue.pop(0)\n",
    "            visited[cur] = True\n",
    "            if len(hashMap[cur]) > 0:\n",
    "                if target in hashMap[cur]: # 在这里判断有没有target\n",
    "                    return True\n",
    "                for point in hashMap[cur]:\n",
    "                    if not visited[point]:\n",
    "                        queue.append(point)\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        # if start == target:\n",
    "        #     return True\n",
    "\n",
    "        # hashMap = collections.defaultdict(set)\n",
    "        # for key, val in graph:\n",
    "        #     hashMap[key].add(val)\n",
    "        \n",
    "        # signed = [False] * n\n",
    "        # dq = deque([start])\n",
    "\n",
    "        # while dq:\n",
    "        #     cur = dq.popleft()\n",
    "        #     signed[cur] = True\n",
    "        #     if len(hashMap[cur]) > 0:\n",
    "        #         if target in hashMap[cur]:\n",
    "        #             return True\n",
    "        #         for val in hashMap[cur]:\n",
    "        #             if not signed[val]:\n",
    "        #                 dq.append(val)\n",
    "        \n",
    "        # return False\n",
    "\n",
    "        if start==target:\n",
    "            return True\n",
    "        # 构建邻接表\n",
    "        hashMap = defaultdict(set)\n",
    "        for key, value in graph:  # 用字典来构建邻接表\n",
    "            hashMap[key].add(value)\n",
    "        visited = [False] * n # 记录遍历过的顶点，防止环的情况出现\n",
    "        queue = []\n",
    "        queue.append(start)\n",
    "        while queue:\n",
    "            cur = queue.pop(0)\n",
    "            visited[cur] = True\n",
    "            if len(hashMap[cur]) > 0:\n",
    "                if target in hashMap[cur]: # 在这里判断有没有target\n",
    "                    return True\n",
    "                for point in hashMap[cur]:\n",
    "                    if not visited[point]:\n",
    "                        queue.append(point)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        node2node = defaultdict(set)\n",
    "        for n_1, n_2 in graph:\n",
    "            node2node[n_1].add(n_2)\n",
    "        \n",
    "        visited = [False] * n\n",
    "        nodes = deque([start])\n",
    "\n",
    "        while nodes:\n",
    "            node = nodes.popleft()\n",
    "            if visited[node]:\n",
    "                continue\n",
    "            visited[node] = True\n",
    "            if node == target:\n",
    "                return True\n",
    "            nodes.extend(node2node[node])\n",
    "        \n",
    "        return False\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        from collections import defaultdict\n",
    "        g = defaultdict(set)\n",
    "        for u, v in graph:\n",
    "            g[u].add(v)\n",
    "        vis = [False] * n\n",
    "\n",
    "        def bfs(u):\n",
    "            from collections import deque\n",
    "            q = deque([u])\n",
    "            while q:\n",
    "                cur = q.popleft()\n",
    "                vis[cur] = True\n",
    "                if cur == target:\n",
    "                    return True\n",
    "                for v in g[cur]:\n",
    "                    if not vis[v]:\n",
    "                        q.append(v)\n",
    "            return False\n",
    "        return bfs(start)\n",
    "\n",
    "        def dfs(u):\n",
    "            vis[u] = True\n",
    "            if u == target:\n",
    "                return True\n",
    "            for v in g[u]:\n",
    "                if not vis[v] and dfs(v):\n",
    "                    return True\n",
    "            return False\n",
    "        return dfs(start)\n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "3\n",
    "[[0, 1], [0, 2], [1, 2], [1, 2]]\n",
    "0\n",
    "2\n",
    "5\n",
    "[[0, 1], [0, 2], [0, 4], [0, 4], [0, 1], [1, 3], [1, 4], [1, 3], [2, 3], [3, 4]]\n",
    "0\n",
    "4\n",
    "\n",
    "4\n",
    "[[0, 1], [0, 2], [1, 2], [2, 0], [3, 2]]\n",
    "0\n",
    "3\n",
    "\n",
    "25\n",
    "[[0, 1], [0, 3], [0, 10], [0, 18], [1, 2], [1, 7], [1, 11], [1, 12], [2, 4], [2, 5], [2, 13], [2, 16], [3, 6], [3, 8], [4, 9], [5, 17], [7, 20], [7, 22], [8, 10], [10, 19], [11, 15], [13, 14], [14, 21], [15, 23], [19, 24], [20, 22]]\n",
    "0\n",
    "12\n",
    "\n",
    "12\n",
    "[[0, 1], [1, 2], [1, 3], [1, 10], [1, 11], [1, 4], [2, 4], [2, 6], [2, 9], [2, 10], [2, 4], [2, 5], [2, 10], [3, 7], [3, 7], [4, 5], [4, 11], [4, 11], [4, 10], [5, 7], [5, 10], [6, 8], [7, 11], [8, 10]]\n",
    "2\n",
    "3\n",
    "\n",
    "0 <= n <= 100000\n",
    "All node numbers are within the range [0, n].\n",
    "There might be self cycles and duplicated edges.\n",
    "\n",
    "Depth-First Search, Breadth-First Search, Graph\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        if start == target: return True\n",
    "        g = [[] for _ in range(n)]\n",
    "        for p in graph:\n",
    "            g[p[0]].append(p[1])\n",
    "        que = deque([start])\n",
    "        vis = [False]*n\n",
    "        while que:\n",
    "            curr = que.popleft()\n",
    "            for nxt in g[curr]:\n",
    "                if nxt == target: return True\n",
    "                if nxt in vis: continue\n",
    "                vis[nxt] = True\n",
    "                que.append(nxt)\n",
    "        return False\n",
    "    \"\"\"\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        if start == target: return True\n",
    "        g = [set() for _ in range(n)]\n",
    "        for p in graph:\n",
    "            g[p[0]].add(p[1])\n",
    "        vis = set([start])\n",
    "        return self.dfs(g, vis, start, target)\n",
    "    def dfs(self, g, vis, start, target):\n",
    "        if target in g[start]: return True\n",
    "        for nxt in g[start]:\n",
    "            if nxt in vis: continue\n",
    "            vis.add(nxt)\n",
    "            if self.dfs(g, vis, nxt, target): return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        if start == target:\n",
    "            return True\n",
    "        g = [set() for _ in range(n)]\n",
    "        for e in graph:\n",
    "            g[e[0]].add(e[1])\n",
    "        q, head = [start], -1\n",
    "        visited = [False] * n\n",
    "        visited[start] = True\n",
    "        while head + 1 < len(q):\n",
    "            head += 1\n",
    "            u = q[head]\n",
    "            for v in g[u]:\n",
    "                if not visited[v]:\n",
    "                    if v == target:\n",
    "                        return True\n",
    "                    q.append(v)\n",
    "                    visited[v] = True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        if start == target:\n",
    "            return True\n",
    "        visited = [0]*n\n",
    "        g = [set() for i in range(n)]\n",
    "        print(g)\n",
    "        for x in graph:\n",
    "            print('============》》》》')\n",
    "            print(g[x[0]])\n",
    "            g[x[0]].add(x[1])\n",
    "            print(g[x[0]])\n",
    "        print(g)\n",
    "        if target in g[start]:\n",
    "            return True\n",
    "        q = collections.deque([start])\n",
    "        visited[start] = 1\n",
    "        while len(q) > 0:\n",
    "            len_q = len(q)\n",
    "            for i in range(len(q)):\n",
    "                top = q.popleft()\n",
    "                if top == target:\n",
    "                    return True\n",
    "                for x in g[top]:\n",
    "                    if visited[x] == 0:\n",
    "                        q.append(x)\n",
    "                        visited[x] = 1\n",
    "        return False\n",
    "                        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        mp = {i:[] for i in range(n)}\n",
    "        for a,b in graph:\n",
    "            mp[a].append(b)\n",
    "            # mp[b].append(a)\n",
    "        visited = set()\n",
    "        flag = False\n",
    "        def dfs(start):\n",
    "            nonlocal mp,visited,flag\n",
    "            if target in mp[start]:\n",
    "                 flag |= True\n",
    "            for i in mp[start]:\n",
    "                if i not in visited:\n",
    "                    visited.add(i)\n",
    "                    dfs(i)\n",
    "                    visited.remove(i)\n",
    "        dfs(start)\n",
    "        return flag\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph, start: int, target: int) -> bool:\n",
    "        d = defaultdict(list)\n",
    "        for i1,i2 in graph:\n",
    "            if i2 not in d[i1]:\n",
    "                d[i1].append(i2)\n",
    "        vis = defaultdict(list)\n",
    "        q = deque()\n",
    "        q.append(start)\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                x = q.popleft()\n",
    "                leaves = d[x]\n",
    "                for y in leaves:\n",
    "                    if y == target:\n",
    "                        return True\n",
    "                    if x not in vis[y] and y not in vis[x]:\n",
    "                        vis[x].append(y)\n",
    "                        vis[y].append(x)\n",
    "                        q.append(y)\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath2(self, n: int, graph: list[list[int]], start: int, target: int) -> bool:\n",
    "        if start == target:\n",
    "            return True\n",
    "\n",
    "        # v1 != v2,\n",
    "        # 从v1到v2的最短路径长度是reach_cost_min[v1][v2]的值, 是len(reach_via[v1][v2]) + 1.\n",
    "        # len(reach_via[v1][v2]) + 2 是包含起点和终点路径上所有的节点数.\n",
    "        reach_cost_min: list[list[int | float]] = [[float(\"inf\")] * n for v in range(n)]\n",
    "        reach_via: list[list[list[int]]] = [[[] for v in range(n)] for v in range(n)]  # 不含起点和终点\n",
    "\n",
    "        for edge in graph:\n",
    "            v1, v2 = edge\n",
    "            if v1 == v2:  # 有向图存在平行边存在自环, 我们要排除这些干扰, 将图转换为没有平行边的有向无环图\n",
    "                continue\n",
    "            reach_cost_min[v1][v2] = min(reach_cost_min[v1][v2], 1)\n",
    "\n",
    "        for v1 in range(n):\n",
    "            for v2 in range(n):\n",
    "                for v3 in range(n):\n",
    "                    if v1 == v2 or v1 == v3 or v2 == v3:\n",
    "                        continue\n",
    "                    if reach_cost_min[v1][v3] + reach_cost_min[v3][v2] < reach_cost_min[v1][v2]:\n",
    "                        reach_cost_min[v1][v2] = reach_cost_min[v1][v3] + reach_cost_min[v3][v2]\n",
    "                        reach_via[v1][v2] = reach_via[v1][v3] + [v3] + reach_via[v3][v2]\n",
    "\n",
    "        # import pprint\n",
    "        # pprint.pprint(reach_cost_min[start][target])\n",
    "        # pprint.pprint(reach_via[start][target])\n",
    "\n",
    "        return reach_cost_min[start][target] != float(\"inf\")\n",
    "\n",
    "    def findWhetherExistsPath(self, n: int, graph: list[list[int]], start: int, target: int) -> bool:\n",
    "        if start == target:\n",
    "            return True\n",
    "\n",
    "        # 无权重的有向无环图的单源最短路径问题可以使用广度优先遍历,\n",
    "        # 如果是确定起点终点的最短路径问题那么我们可以在找到终点后提前停下来\n",
    "\n",
    "        adj_vs: dict[int, list[int]] = {}\n",
    "        visited: dict[int, bool] = {}\n",
    "        path_length: dict[int, int] = {}\n",
    "        prev_v: dict[int, int] = {}\n",
    "\n",
    "        for v in range(n):\n",
    "            visited[v] = False\n",
    "\n",
    "        for edge in graph:\n",
    "            v1, v2 = edge\n",
    "            if v1 == v2:  # 有向图存在平行边存在自环, 我们要排除这些干扰, 将图转换为没有平行边的有向无环图\n",
    "                continue\n",
    "            adj_vs.setdefault(v1, []).append(v2)\n",
    "\n",
    "        from collections import deque\n",
    "        # v_pairs 的元素是 tuple[v, prev]\n",
    "        v_pairs: deque[tuple[int, int]] = deque()\n",
    "        v_pairs.append((start, start))\n",
    "\n",
    "        length: int = 0\n",
    "        n_vs_in_this_round: int = 1\n",
    "        while len(v_pairs) > 0:\n",
    "\n",
    "            for i in range(n_vs_in_this_round):\n",
    "                v, prev = v_pairs.popleft()\n",
    "                if visited[v] is True:  # 只能在这里判断visited\n",
    "                    continue\n",
    "                print(\"visit v\", v)\n",
    "                visited[v] = True\n",
    "                path_length[v] = length\n",
    "                prev_v[v] = prev\n",
    "                for adj_v in adj_vs.get(v, []):  # 不能在此处判断visited, 因为判断后仍然会让一个visited==False的node入队两次\n",
    "                    v_pairs.append((adj_v, v))\n",
    "\n",
    "            length += 1\n",
    "            n_vs_in_this_round = len(v_pairs)\n",
    "\n",
    "        if visited[target]:\n",
    "            print(\"存在可行解.\")\n",
    "            print(\"从起点到终点的 length:\", path_length[target])\n",
    "\n",
    "            nodes_on_path: list[int] = []\n",
    "            node = target\n",
    "            while node != start:\n",
    "                nodes_on_path.append(node)\n",
    "                node = prev_v[node]\n",
    "            nodes_on_path.append(node)\n",
    "            nodes_on_path.reverse()\n",
    "            print(\"从起点到终点的路径:\", nodes_on_path)\n",
    "\n",
    "        return visited[target]\n",
    "\n",
    "\n",
    "# Floyd-Warshall algorithm 是解决任意两点间的最短路径的一种算法, 可以正确处理有向图或负权（但不可存在负权回路）的最短路径问题.\n",
    "# 复杂度 N^3 (N是节点数目)\n",
    "#\n",
    "#\n",
    "# https://zh.wikipedia.org/wiki/最短路问题\n",
    "# 最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。算法具体的形式包括：\n",
    "#\n",
    "#     确定起点的最短路径问题(Single-destination shortest-paths problem)\n",
    "#         也叫单源最短路问题，即已知起始结点，求最短路径的问题。\n",
    "#         在边权非负时适合使用Dijkstra算法，若边权为负时则适合使用Bellman-ford算法或者SPFA算法。\n",
    "#\n",
    "#     确定终点的最短路径问题\n",
    "#         与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。\n",
    "#         在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。\n",
    "#\n",
    "#     确定起点终点的最短路径问题(Single-pair shortest-path problem)\n",
    "#         即已知起点和终点，求两结点之间的最短路径。\n",
    "#         Introduction to Algorithms 4ed:\n",
    "#             Find a shortest path from u to v for\n",
    "#             given vertices u and v. If you solve the single-source problem with\n",
    "#             source vertex u, you solve this problem also. Moreover, all known\n",
    "#             algorithms for this problem have the same worst-case asymptotic\n",
    "#             running time as the best single-source algorithms.\n",
    "#         如果我们能找到一个有效的 heuristic function, 可以使用 A* 搜索.\n",
    "#\n",
    "#     全局最短路径问题(All-pairs shortest-paths problem)\n",
    "#         也叫多源最短路问题，求图中所有的最短路径。适合使用Floyd-Warshall算法。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "\n",
    "        q = deque([start])\n",
    "\n",
    "        set_graph = defaultdict(set)\n",
    "\n",
    "        for st, end in graph:\n",
    "            set_graph[st].add(end)\n",
    "            set_graph[end] = set_graph[end]\n",
    "        # print(set_graph , target)\n",
    "        if start not in set_graph.keys() or target not in set_graph.keys():\n",
    "            return False \n",
    "        while q :\n",
    "\n",
    "            node = q.popleft()\n",
    "            \n",
    "            for j in set_graph[node]:\n",
    "                if j == target:\n",
    "                    return True\n",
    "                else : q.append(j)\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        edges = collections.defaultdict(set)\n",
    "        for f, t in graph:\n",
    "            edge = edges[f]\n",
    "            edge.add(t)\n",
    "\n",
    "        ss = edges[start]\n",
    "        while ss:\n",
    "            if target in ss: return True\n",
    "            next = ss.pop()\n",
    "            tmp = edges[next]\n",
    "            ss |= tmp\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        k = defaultdict(set)\n",
    "        for i in graph:\n",
    "            k[i[0]].add(i[1])\n",
    "        print(k)\n",
    "\n",
    "        global ans\n",
    "        ans = False\n",
    "        def dfs(start):\n",
    "            global ans\n",
    "            print(type(start),start,type(target),target)\n",
    "            if start == target:\n",
    "                ans = True\n",
    "                return\n",
    "            if start == set():\n",
    "                ans = False\n",
    "            for i in k[start]:\n",
    "                dfs(i)\n",
    "        dfs(start)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        def reachable(u):\n",
    "            if u == target:\n",
    "                return True\n",
    "            if u in visited:\n",
    "                return False\n",
    "            visited.add(u)\n",
    "            for v in links[u]:\n",
    "                if reachable(v):\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        links = [set() for _ in range(n)]\n",
    "        for u, v in graph:\n",
    "            links[u].add(v)\n",
    "        visited = set()\n",
    "        return reachable(start)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        map_ = [set() for i in range(n)]\n",
    "        for a, b in graph:\n",
    "            map_[a].add(b)\n",
    "\n",
    "        def dfs(idx):\n",
    "            set_= map_[idx]\n",
    "            if target in set_: return True\n",
    "            for i in set_:\n",
    "                if dfs(i): return True\n",
    "            return False\n",
    "        \n",
    "        return dfs(start)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        # BFS\n",
    "        rec = defaultdict(set)\n",
    "        for f, t in graph:\n",
    "            rec[f].add(t)\n",
    "        \n",
    "        q = [start]\n",
    "        visited = set()\n",
    "\n",
    "        while q:\n",
    "            n = q.pop(0)\n",
    "            for x in list(rec[n]):\n",
    "                if x == target:\n",
    "                    return True\n",
    "                if x not in visited:\n",
    "                    visited.add(x)\n",
    "                    q.append(x)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        if start == target or [start, target] in graph:\n",
    "            return True\n",
    "        hlp = defaultdict(set)\n",
    "        q = deque([])\n",
    "        visit = set([start])\n",
    "        for a, b in graph:\n",
    "            if a == start:\n",
    "                if b not in visit:\n",
    "                    if b == target:\n",
    "                        return True\n",
    "                    q.append(b)\n",
    "                    visit.add(b)\n",
    "            else:\n",
    "                hlp[a].add(b)\n",
    "        while q:\n",
    "            cur = q.popleft()\n",
    "            for nxt in hlp[cur]:\n",
    "                if nxt not in visit:\n",
    "                    if nxt == target:\n",
    "                        return True\n",
    "                    q.append(nxt)\n",
    "                    visit.add(nxt)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import  defaultdict\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        #构建邻接表,集合字典\n",
    "        hashmap = defaultdict(set)\n",
    "        for i,j in graph:\n",
    "            hashmap[i].add(j)\n",
    "        if start==target:\n",
    "            return True\n",
    "        queue = []\n",
    "        queue.append(start)\n",
    "        seen = set()       \n",
    "        while queue:\n",
    "            vertex=queue.pop(0)\n",
    "            seen.add(vertex)\n",
    "            nodes = hashmap[vertex]\n",
    "            if nodes != 0:\n",
    "                if target in nodes:\n",
    "                    return True\n",
    "                for w in nodes:\n",
    "                    if  w not in seen:\n",
    "                        queue.append(w)                      \n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... 188 ms ... 49 % ... 65.2 MB ... 8 %\n",
    "        #  time: O(V+E)\n",
    "        # space: O(V+E)\n",
    "        \n",
    "        if start == target:\n",
    "            return True\n",
    "        conn = collections.defaultdict(set)\n",
    "        for u, v in graph:\n",
    "            conn[u].add(v)\n",
    "        level = {start}\n",
    "        visit = {start}\n",
    "        while level:\n",
    "            nextlevel = set()\n",
    "            for prev in level:\n",
    "                for curr in conn[prev]:\n",
    "                    if curr == target:\n",
    "                        return True\n",
    "                    if curr not in visit:\n",
    "                        nextlevel.add(curr)\n",
    "                        visit.add(curr)\n",
    "            level = nextlevel\n",
    "        return False\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        g = [set() for _ in range(n)]\n",
    "        for e in graph:\n",
    "            if e[0] != e[1]:\n",
    "                g[e[0]].add(e[1])\n",
    "        visted = [False] * n\n",
    "\n",
    "        def dfs(node):\n",
    "            visted[node] = True\n",
    "            for nextnode in g[node]:\n",
    "                if not visted[nextnode]:\n",
    "                    if nextnode == target:\n",
    "                        return True\n",
    "                    if dfs(nextnode):\n",
    "                        return True\n",
    "            return False\n",
    "\n",
    "        return dfs(start)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        def dfs(x):\n",
    "            vis[x] = True\n",
    "            if x == target:\n",
    "                return\n",
    "\n",
    "            for y in hash_map[x]:\n",
    "                if not vis[y]:\n",
    "                    dfs(y)\n",
    "\n",
    "        hash_map = {}\n",
    "        for i in range(n):\n",
    "            hash_map[i] = []\n",
    "        for x, y in graph:\n",
    "            hash_map[x].append(y)\n",
    "\n",
    "        vis = [False] * n\n",
    "\n",
    "        dfs(start)\n",
    "        return vis[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        if start == target:\n",
    "            return True\n",
    "        cnt = defaultdict(set)\n",
    "        visit = set([start])\n",
    "        for i, j in graph:\n",
    "            cnt[i].add(j)\n",
    "        deq = deque([start])\n",
    "        while deq:\n",
    "            nodes = cnt[deq.popleft()]\n",
    "            if target in nodes:\n",
    "                return True\n",
    "            for node in nodes:\n",
    "                if node not in visit:\n",
    "                    deq.append(node)\n",
    "                    visit.add(node)\n",
    "        return False\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution0:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        edges = defaultdict(set)\n",
    "\n",
    "        for s, t in graph:\n",
    "            edges[s].add(t)\n",
    "\n",
    "        def dfs(s, visited: set):\n",
    "            for t in edges[s]:\n",
    "                if t == target:\n",
    "                    return True\n",
    "\n",
    "                if t not in visited:\n",
    "                    visited.add(t)\n",
    "                    found = dfs(t, visited)\n",
    "                    if found:\n",
    "                        return True\n",
    "                    visited.remove(t)\n",
    "\n",
    "            return False\n",
    "\n",
    "        return dfs(start, set())\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        edges = defaultdict(set)\n",
    "\n",
    "        for s, t in graph:\n",
    "            edges[s].add(t)\n",
    "\n",
    "        q = deque([start])\n",
    "        visited = set()\n",
    "\n",
    "        while q:\n",
    "            s = q.popleft()\n",
    "            for t in edges[s]:\n",
    "                if t == target:\n",
    "                    return True\n",
    "                if t not in visited:\n",
    "                    q.append(t)\n",
    "                    visited.add(t)\n",
    "\n",
    "        return False\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        g = defaultdict(set)\n",
    "        for x, y in graph:\n",
    "            g[x].add(y)\n",
    "\n",
    "        dis = [inf] * n\n",
    "        dis[start] = 0\n",
    "        # vis = [0] * n\n",
    "        q = [(start, 0)]\n",
    "        while q:\n",
    "            v, d = heappop(q)\n",
    "            # if vis[v]:\n",
    "            #     continue\n",
    "            # vis[v] = 1\n",
    "            if d > dis[v]:\n",
    "                continue\n",
    "            for u in g[v]:\n",
    "                if d + 1 < dis[u]:\n",
    "                    dis[u] = d + 1\n",
    "                    heappush(q, (u, d + 1))\n",
    "        # print(dis)\n",
    "        return dis[target] != inf\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        adjList = defaultdict(set)\n",
    "        for u, v in graph:\n",
    "            adjList[u].add(v)\n",
    "\n",
    "        q = [start]\n",
    "        vis = set(q)\n",
    "        while q:\n",
    "            nxt = []\n",
    "            for u in q:\n",
    "                if u == target:\n",
    "                    return True\n",
    "                for v in adjList[u]:\n",
    "                    if v not in vis:\n",
    "                        nxt.append(v)\n",
    "                        vis.add(v)\n",
    "            q = nxt\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        vis = set()\n",
    "        dic = defaultdict(set)\n",
    "        for i, j in graph:\n",
    "            dic[i].add(j)\n",
    "        q = deque([start])\n",
    "\n",
    "        while q:\n",
    "            cur = q.popleft()\n",
    "            if cur == target:\n",
    "                return True\n",
    "            vis.add(cur)\n",
    "            for idx in dic[cur]:\n",
    "                if idx not in vis:\n",
    "                    q.append(idx)\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        path = [set() for _ in range(n)]\n",
    "        for i, j in graph:\n",
    "            path[i].add(j)\n",
    "\n",
    "        searched = set()\n",
    "        tosearch = path[start]\n",
    "\n",
    "        while tosearch:\n",
    "            next_tosearch = set()\n",
    "            if target in tosearch:\n",
    "                return True\n",
    "            searched = searched.union(tosearch)\n",
    "            for i in tosearch:\n",
    "                for j in path[i]:\n",
    "                    if j not in searched: \n",
    "                        next_tosearch.add(j)\n",
    "            tosearch = next_tosearch\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, graph, start, target):\n",
    "        if target == start:\n",
    "            return True\n",
    "\n",
    "        if target in graph[start]:\n",
    "            return True\n",
    "\n",
    "        for p in graph[start]:\n",
    "            if self.dfs(graph, p, target):\n",
    "                return True\n",
    "\n",
    "        return False\n",
    "\n",
    "\n",
    "\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        node = {}\n",
    "\n",
    "        for i in range(n):\n",
    "            node[i] = set()\n",
    "\n",
    "        for edge in graph:\n",
    "            s, e = edge\n",
    "            node[s].add(e)\n",
    "\n",
    "        return self.dfs(node, start, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, graph, start, target):\n",
    "        if target == start:\n",
    "            return True\n",
    "\n",
    "        if target in graph[start]:\n",
    "            return True\n",
    "\n",
    "        for p in graph[start]:\n",
    "            if self.dfs(graph, p, target):\n",
    "                return True\n",
    "\n",
    "        return False\n",
    "\n",
    "\n",
    "\n",
    "    def bfs(self, graph, start, target):\n",
    "        queue = [start]\n",
    "        while len(queue) > 0:\n",
    "            p = queue.pop(0)\n",
    "            if p == target:\n",
    "                return True\n",
    "            for q in graph[p]:\n",
    "                queue.append(q)\n",
    "        return False\n",
    "\n",
    "\n",
    "\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        node = {}\n",
    "\n",
    "        for i in range(n):\n",
    "            node[i] = set()\n",
    "\n",
    "        for edge in graph:\n",
    "            s, e = edge\n",
    "            node[s].add(e)\n",
    "\n",
    "        return self.bfs(node, start, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        g = {i:set() for i in range(n)}\n",
    "        for a,b in graph:\n",
    "            if a!=b:g[a].add(b)\n",
    "        q = [start]\n",
    "        visit = set()\n",
    "        while q:\n",
    "            node = q.pop()\n",
    "            if node == target:return True\n",
    "            visit.add(node)\n",
    "            for nei in g[node] - visit:\n",
    "                q.append(nei)\n",
    "        return target in visit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        visited = [0] * n\n",
    "        loads = defaultdict(set)\n",
    "        for x,y in graph:\n",
    "            loads[x].add(y)\n",
    "        print(loads)\n",
    "\n",
    "        def DFS(node,target):\n",
    "            visited[node] = 1\n",
    "            if node == target:\n",
    "                return True\n",
    "            res = False\n",
    "            for nxt in loads[node]:\n",
    "                if visited[nxt] == 0:\n",
    "                    res |= DFS(nxt,target)\n",
    "            return res\n",
    "        \n",
    "        return DFS(start,target)\n",
    "\n",
    "\n",
    "                \n",
    "            \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def _make_connection(self, n, graph):\n",
    "        output_dict = {i: set() for i in range(n)}\n",
    "        for per_connect in graph:\n",
    "            source, target = per_connect\n",
    "            output_dict[source].add(target)\n",
    "        return output_dict\n",
    "\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        if start == target:\n",
    "            return True\n",
    "        connection_dict = self._make_connection(n, graph)\n",
    "        visited = [start]\n",
    "        to_reach = list(connection_dict[start])\n",
    "        while to_reach:\n",
    "            cur_node = to_reach.pop()\n",
    "            if cur_node == target:\n",
    "                return True\n",
    "            if cur_node in visited:\n",
    "                continue\n",
    "            to_reach += list(connection_dict[cur_node])\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        self.adjacent = {i: set() for i in range(n)}   # 每个节点 可以指向的那些点\n",
    "        for i in graph:\n",
    "            self.adjacent[i[0]].add(i[1])   # 图里存在 从i0指向i1的边\n",
    "        self.visited = [False] * n\n",
    "\n",
    "        self.dfs(start, target)\n",
    "        return self.found\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.found = False\n",
    "\n",
    "    def dfs(self, cur, target):\n",
    "        if self.found:   # 这个剪枝 可以不加\n",
    "            return\n",
    "        if cur == target:\n",
    "            self.found = True\n",
    "            return\n",
    "        self.visited[cur] = True\n",
    "        for i in self.adjacent[cur]:\n",
    "            if self.visited[i]:\n",
    "                continue\n",
    "            self.dfs(i, target)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:\n",
    "        dic_path = defaultdict(set)\n",
    "        for e,v in graph:\n",
    "            dic_path[e].add(v)\n",
    "        visited = set()\n",
    "\n",
    "        queue = deque()\n",
    "        queue.append(start)\n",
    "        while queue:\n",
    "            pos = queue.popleft()\n",
    "            visited.add(pos)\n",
    "            for x in dic_path[pos]:\n",
    "                if x == target:\n",
    "                    return True\n",
    "                else:\n",
    "                    if x not in visited:\n",
    "                        queue.append(x)\n",
    "        return False\n",
    "    \n",
    "        \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
